package basic.study.algorithms.solution.DynamicProgramming;

/**
 * @author Kevin
 * @date 2020/2/18 20:22
 */
public class YangHuiTriangle {
    static int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};

    public static void main(String[] args) {
        int[][] states = new int[matrix.length][matrix.length];
        states[0][0] = matrix[0][0];

        for (int i = 1; i < matrix.length; i++) {//动态规划
            for (int j = 0; j < matrix[i].length; j++) {
                if (j == 0) states[i][j] = states[i-1][j] + matrix[i][j];//如果j是层的头结点
                else if (j == matrix[i].length-1) states[i][j] = states[i-1][j-1] + matrix[i][j];//如果j是层的尾结点
                else {
                    int top1 = states[i-1][j-1];
                    int top2 = states[i-1][j];
                    states[i][j] = Math.min(top1, top2) + matrix[i][j];//节点值取两个父节点中小的
                }
            }
        }

        //如果问的是路径
        int j = -1;
        int minVal = Integer.MAX_VALUE;
        for (int i = matrix[matrix.length-1].length-1; i>= 0; i--){//最后一层，从尾开始遍历
            if (states[matrix.length-1][i] < minVal) {
                j = i;
                minVal = states[matrix.length-1][i];
            }
        }

        System.out.println("最小值: " + String.valueOf(minVal));

        //找到了最小值、和对应的点坐标，遍历往上
        for (int i = matrix.length-1; i >= 0; i--) {
            System.out.println("节点: " + String.valueOf(matrix[i][j]));
            if (i != 0) {
                if (j == 0) {}//j为头节点时，j不变
                else if(j == matrix[i].length-1) {j = j-1;}//j为尾节点时，为上一层尾结点
                else {
                    if (states[i][j] - matrix[i][j] == states[i-1][j-1]) {//如果是左上节点
                        j = j-1;
                    } else {
                        //如果是右上节点
                    }
                }
            }
        }

    }
}
